package com.example.niuke;

import com.alibaba.fastjson.JSON;

/**
 * 300. 最长递增子序列
 * 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
 * <p>
 * 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [10,9,2,5,3,7,101,18]
 * 输出：4
 * 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
 * <p>
 * 示例 2：
 * 输入：nums = [0,1,0,3,2,3]
 * 输出：4
 * <p>
 * 思路：
 * 要求是把乱序的数组中抽离出一条递增的序列，所以每个数值间隔最小就是最佳情况
 * 我们维护一个数组 d[i] ，表示长度为 ii 的最长上升子序列的末尾元素的最小值，用 len 记录目前最长上升子序列的长度，起始时len 为 1，d[1]=nums[0]
 * 最后整个算法流程为：
 * 设当前已求出的最长上升子序列的长度为 len（初始时为 11），从前往后遍历数组 nums，在遍历到 nums[i] 时：
 * <p>
 * 如果 nums[i]>d[len]  ，则直接加入到 dd 数组末尾，并更新 len=len+1；
 * <p>
 * 否则，在d数组中二分查找，找到第一个比 nums[i] 小的数 d[k] ，并更新d[k+1]=nums[i]。
 * 最后返回是以 原数组和dp数组从后往前遍历，如果dp[i]==len 说明这个值就是子序列的一员，在原数组中取出放入结果数组。
 * <p>
 * <p>
 * 1.初始化end数组存放列表最大子列，初始化dp代表第i个元素时它的最大子序列个数
 * 2.从前往后遍历初始数组，维护长度变量len。
 * 3。如果当前元素大于end数组最后一个值，则加入后面。否则二分查找适当位置插入到end数组中
 */
public class Thelongestincreasingsubsequence {
    public static void main(String[] args) {
        Thelongestincreasingsubsequence thelongestincreasingsubsequence = new Thelongestincreasingsubsequence();
        int[] a = {4, 5, 1, 2, 6};
        System.out.println(JSON.toJSONString(thelongestincreasingsubsequence.LIS(a)));
        System.out.println(JSON.toJSONString(thelongestincreasingsubsequence.lengthOfLIS(a)));
    }

    /**
     * retrun the longest increasing subsequence
     *
     * @param arr int整型一维数组 the array
     * @return int整型一维数组
     */
    public int[] LIS(int[] arr) {
        int n = arr.length;
        // 列表的最大子序列 下标从1开始
        int[] end = new int[n + 1];
        // 存储每个元素的最大子序列个数
        int[] dp = new int[n];
        int len = 1;
        //子序列的第一个元素默认为数组第一个元素
        end[1] = arr[0];
        //第一个元素的最大子序列个数肯定是1
        dp[0] = 1;
        for (int i = 0; i < n; i++) {
            if (end[len] < arr[i]) {
                //当arr[i] > end[len] 时 arr[i]添加到 end后面
                end[++len] = arr[i];
                dp[i] = len;
            } else {
                // 当前元素小于end中的最后一个元素 利用二分法寻找第一个大于arr[i]的元素
                // end[l] 替换为当前元素 dp[]
                int l = 0;
                int r = len;
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (end[mid] >= arr[i]) {
                        r = mid - 1;
                    } else {
                        l = mid + 1;
                    }
                }
                end[l] = arr[i];
                dp[i] = l;
            }
        }
//从后开始遍历的原因是 如果小值在后面，可能会前插入dp数组进行覆盖，（如果大的值和小的值数量相等5，6，7，1，2，3）
        //则123肯定会先遍历到直接返回，如果是123456那么整体就是一个有序，则无需关心。
        // 总而言之：如果有多个有序数列大小相等，那么小的一定会先遍历到，如果没有，那么最大值只有一个，也会最终排出最小的队列
        int[] res = new int[len];
        for (int i = n - 1; i >= 0; i--) {
            if (dp[i] == len) {
                res[--len] = arr[i];
            }
        }
        return res;
    }

    public int lengthOfLIS(int[] nums) {
        int len = 1, n = nums.length;
        if (n == 0) {
            return 0;
        }
        int[] d = new int[n + 1];
        d[len] = nums[0];
        for (int i = 1; i < n; ++i) {
            if (nums[i] > d[len]) {
                d[++len] = nums[i];
            } else {
                // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
                int l = 1, r = len, pos = 0;
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (d[mid] < nums[i]) {
                        pos = mid;
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                d[pos + 1] = nums[i];
            }
        }
        return len;
    }


}



